home *** CD-ROM | disk | FTP | other *** search
/ SGI Developer Toolbox 6.1 / SGI Developer Toolbox 6.1 - Disc 4.iso / public / agrep / mgrep.c < prev    next >
C/C++ Source or Header  |  1994-08-01  |  8KB  |  324 lines
  1. /* Copyright (c) 1991 Sun Wu and Udi Manber.  All Rights Reserved. */
  2. /* multipattern matcher */
  3. #include <stdio.h>
  4. #include <ctype.h>
  5. #define MAXPAT  256
  6. #define MAXLINE 1024
  7. #define MAXSYM  256
  8. #define MAXMEMBER1 4096
  9. #define MAXPATFILE 260000
  10. #define BLOCKSIZE  8192
  11. #define MAXHASH    8192
  12. #define mm        8191
  13. #define max_num    30000  
  14. #define W_DELIM       128
  15. #define L_DELIM    10 
  16.  
  17. extern COUNT, FNAME, SILENT, FILENAMEONLY, num_of_matched;
  18. extern INVERSE;
  19. extern WORDBOUND, WHOLELINE, NOUPPER;
  20. extern unsigned char  CurrentFileName[], Progname[]; 
  21. extern total_line;
  22.  
  23. int LONG  = 0;
  24. int SHORT = 0;
  25. int p_size=0;
  26. unsigned char SHIFT1[MAXMEMBER1];
  27. unsigned char tr[MAXSYM];
  28. unsigned char tr1[MAXSYM];
  29. struct pat_list {
  30.     int  index;
  31.     struct pat_list *next;
  32. } *HASH[MAXHASH];
  33. struct pat_list  *pt, *qt;
  34. unsigned char buf[MAXPATFILE+BLOCKSIZE];
  35. unsigned char pat_spool[MAXPATFILE+2*max_num+MAXPAT];
  36. unsigned char *patt[max_num];
  37. unsigned char pat_len[max_num];
  38.  
  39.  
  40. prepf(fp)
  41. int fp;
  42. {
  43.     int length=0, i, p=1, pdx=0, num_pat;
  44.     unsigned char *pat_ptr=pat_spool, temp[10];
  45.     unsigned Mask = 15;
  46.     int num_read;
  47.  
  48.     while((num_read = read(fp, buf+length, BLOCKSIZE)) > 0) {
  49.     length = length + num_read;
  50.     if(length > MAXPATFILE) {
  51.         fprintf(stderr, "%s: maximum pattern file size is %d\n", Progname, MAXPATFILE);
  52.         exit(2);
  53.     }
  54.     }
  55.     buf[length] = '\n';
  56.     i = 0; p=1;
  57.     while(i<length) {
  58.     patt[p] = pat_ptr;
  59.     if(WORDBOUND) *pat_ptr++ = W_DELIM;
  60.     if(WHOLELINE) *pat_ptr++ = L_DELIM;
  61.     while((*pat_ptr = buf[i++]) != '\n') pat_ptr++;
  62.     if(WORDBOUND) *pat_ptr++ = W_DELIM;
  63.     if(WHOLELINE) *pat_ptr++ = L_DELIM;           /* Can't be both on */
  64.     *pat_ptr++ = 0;
  65.     p++;  
  66.     }
  67.     if(p>max_num) {
  68.     fprintf(stderr, "%s: maximum number of patterns is %d\n", Progname, max_num); 
  69.     exit(2);
  70.     }
  71.     for(i=1; i<20; i++) *pat_ptr = i;  /* boundary safety zone */
  72.     for(i=0; i< MAXSYM; i++) tr[i] = i;
  73.     if(NOUPPER) {
  74.     for(i='A'; i<= 'Z'; i++) tr[i] = i + 'a' - 'A';
  75.     }
  76.     if(WORDBOUND) {
  77.     for(i=0; i<128; i++) if(!isalnum(i)) tr[i] = W_DELIM;
  78.     }
  79.     for(i=0; i< MAXSYM; i++) tr1[i] = tr[i]&Mask;
  80.     num_pat = p-1;
  81.     p_size = MAXPAT;
  82.     for(i=1 ; i <= num_pat; i++) {
  83.     p = strlen(patt[i]);
  84.     pat_len[i] = p;
  85.     if(p!=0 && p < p_size) p_size = p;
  86.     }
  87.     if(p_size == 0) {
  88.     fprintf(stderr, "%s: the pattern file is empty\n");
  89.     exit(2);
  90.     }
  91.     if(length > 400 && p_size > 2) LONG = 1;
  92.     if(p_size == 1) SHORT = 1;
  93.     for(i=0; i<MAXMEMBER1; i++) SHIFT1[i] = p_size - 2;
  94.     for(i=0; i<MAXHASH; i++) {
  95.     HASH[i] = 0;
  96.     }
  97.     for(i=1; i<= num_pat; i++) f_prep(i, patt[i]);
  98. }
  99.  
  100.  
  101. mgrep(fd)
  102. int fd;
  103. { 
  104.     register char r_newline = '\n';
  105.     unsigned char text[2*BLOCKSIZE+MAXLINE]; 
  106.     register int buf_end, num_read, i=0, j, start, end, residue = 0;
  107.  
  108.     text[MAXLINE-1] = '\n';  /* initial case */
  109.     start = MAXLINE-1;
  110.  
  111.     while( (num_read = read(fd, text+MAXLINE, BLOCKSIZE)) > 0) 
  112.     {
  113.        if(INVERSE && COUNT) countline(text+MAXLINE, num_read);
  114.        buf_end = end = MAXLINE + num_read -1 ;
  115.        while(text[end]  != r_newline && end > MAXLINE) end--;
  116.        residue = buf_end - end  + 1 ;
  117.        text[start-1] = r_newline;
  118.        if(SHORT) m_short(text, start, end);
  119.        else      monkey1(text, start, end);
  120.        if(FILENAMEONLY && num_of_matched) {
  121.         printf("%s\n", CurrentFileName);
  122.         return;
  123.        }
  124.        start = MAXLINE - residue;
  125.        if(start < 0) {
  126.             start = 1; 
  127.        }
  128.        strncpy(text+start, text+end, residue);
  129.     } /* end of while(num_read = ... */
  130.     text[MAXLINE] = '\n';
  131.     text[start-1] = '\n';
  132.     if(residue > 1) {
  133.         if(SHORT) m_short(text, start, end);
  134.         else      monkey1(text, start, end);
  135.     }
  136.     return;
  137. } /* end mgrep */
  138.  
  139. countline(text, len)
  140. unsigned char *text; int len;
  141. {
  142. int i;
  143.     for (i=0; i<len; i++) if(text[i] == '\n') total_line++;
  144. }
  145.  
  146.  
  147. monkey1( text, start, end  ) 
  148. int start, end; register unsigned char *text;
  149. {
  150. register unsigned char *textend;
  151. register unsigned hash, i;
  152. register unsigned char shift; 
  153. register int  m1, j, Long=LONG; 
  154. int pat_index, m=p_size; 
  155. int MATCHED=0;
  156. register unsigned char *qx;
  157. register struct pat_list *p;
  158. unsigned char *lastout;
  159. int OUT=0;
  160.  
  161. textend = text + end;
  162. m1 = m - 1;
  163. lastout = text+start+1;
  164. text = text + start + m1 ;
  165. while (text <= textend) {
  166.     hash=tr1[*text];
  167.     hash=(hash<<4)+(tr1[*(text-1)]);
  168.     if(Long) hash=(hash<<4)+(tr1[*(text-2)]);
  169.     shift = SHIFT1[hash];
  170.     if(shift == 0) {
  171.         hash=0;
  172.         for(i=0;i<=m1;i++)  {
  173.             hash=(hash<<4)+(tr1[*(text-i)]);
  174.         }
  175.         hash=hash&mm;
  176.         p = HASH[hash];
  177.         while(p != 0) {
  178.             pat_index = p->index;
  179.             p = p->next;
  180.             qx = text-m1;
  181.             j = 0;
  182.             while(tr[patt[pat_index][j]] == tr[*(qx++)]) j++;
  183.                 if (j > m1 ) { 
  184.                if(pat_len[pat_index] <= j) {
  185.                 if(text > textend) return;
  186.                         num_of_matched++;
  187.                         if(FILENAMEONLY || SILENT)  return;
  188.                 MATCHED=1;
  189.                     if(COUNT) {
  190.                       while (*text != '\n') text++;
  191.                 }
  192.                 else {
  193.                     if(!INVERSE) {
  194.                       if(FNAME) printf("%s: ",CurrentFileName);
  195.                                   while(*(--text) != '\n');
  196.                                   while(*(++text) != '\n') putchar(*text);
  197.                       printf("\n");
  198.                     }
  199.                     else {
  200.                       if(FNAME) printf("%s: ",CurrentFileName);
  201.                                   while(*(--text) != '\n');
  202.                     if(lastout < text) OUT=1;
  203.                     while(lastout < text) putchar(*lastout++);
  204.                     if(OUT) {
  205.                         putchar('\n');
  206.                         OUT=0;
  207.                     }
  208.                                   while(*(++text) != '\n');
  209.                     lastout=text+1;
  210.                     }
  211.                 }
  212. /*
  213.                 else {
  214.                       if(FNAME) printf("%s: ",CurrentFileName);
  215.                                   while(*(--text) != '\n');
  216.                                   while(*(++text) != '\n') putchar(*text);
  217.                       printf("\n");
  218.                 }
  219. */
  220.                }
  221.                     }
  222.             if(MATCHED) break;
  223.         }
  224.         if(!MATCHED) shift = 1;
  225.         else {
  226.             MATCHED = 0;
  227.             shift = m1;
  228.         }
  229.         }
  230.     text = text + shift;
  231.   }
  232.   if(INVERSE && !COUNT) while(lastout <= textend) putchar(*lastout++);
  233. }
  234.  
  235. m_short( text, start, end  ) 
  236. int start, end; register unsigned char *text;
  237. {
  238. register unsigned char *textend;
  239. register unsigned i; 
  240. register int  j; 
  241. register struct pat_list *p, *q;
  242. register int pat_index; 
  243. int MATCHED=0;
  244. int OUT=0;
  245. unsigned char *lastout;
  246. unsigned char *qx;
  247.  
  248. textend = text + end;
  249. lastout = text + start + 1;
  250. text = text + start - 1 ;
  251. while (++text <= textend) {
  252.         p = HASH[*text];
  253.         while(p != 0) {
  254.             pat_index = p->index;
  255.             p = p->next;
  256.             qx = text;
  257.             j = 0;
  258.             while(tr[patt[pat_index][j]] == tr[*(qx++)]) j++;
  259.             if(pat_len[pat_index] <= j) {
  260.                 if(text >= textend) return;
  261.                         num_of_matched++;
  262.                         if(FILENAMEONLY || SILENT)  return;
  263.                     if(COUNT) {
  264.                       while (*text != '\n') text++;
  265.                 }
  266.                 else {
  267.                       if(FNAME) printf("%s: ",CurrentFileName);
  268.                     if(!INVERSE) {
  269.                                   while(*(--text) != '\n');
  270.                                   while(*(++text) != '\n') putchar(*text);
  271.                       printf("\n");
  272.                     MATCHED = 1;
  273.                     }
  274.                     else {
  275.                                   while(*(--text) != '\n');
  276.                     if(lastout < text) OUT=1;
  277.                     while(lastout < text) putchar(*lastout++);
  278.                     if(OUT) {
  279.                         putchar('\n');
  280.                         OUT=0;
  281.                     }
  282.                                   while(*(++text) != '\n');
  283.                     lastout=text+1;
  284.                     MATCHED = 1;
  285.                     }
  286.                 }
  287.                     }
  288.             if(MATCHED) break;
  289.         }
  290.         MATCHED = 0;
  291.   } /* while */
  292.   if(INVERSE && !COUNT) while(lastout <= textend) putchar(*lastout++);
  293. }
  294.  
  295. f_prep(pat_index, Pattern)
  296. unsigned char *Pattern ; int pat_index;
  297. {
  298. int i, j, m;
  299. register unsigned hash, Mask=15;
  300.     m = p_size;
  301.     for (i = m-1; i>=(1+LONG); i--) {
  302.         hash = (Pattern[i] & Mask);
  303.         hash = (hash << 4) + (Pattern[i-1]& Mask);
  304.         if(LONG) hash = (hash << 4) + (Pattern[i-2] & Mask);
  305.         if(SHIFT1[hash] >= m-1-i) SHIFT1[hash] = m-1-i;
  306.     }
  307.     if(SHORT) Mask = 255;  /* 011111111 */
  308.     hash = 0;
  309.     for(i = m-1; i>=0; i--)  {
  310.         hash = (hash << 4) + (tr[Pattern[i]]&Mask);
  311.     }
  312. /*
  313.     if(INVERSE) hash = Pattern[1];
  314. */
  315.     hash=hash&mm;
  316.     qt = (struct pat_list *) malloc(sizeof(struct pat_list));
  317.     qt->index = pat_index;
  318.     pt = HASH[hash];
  319.     qt->next = pt;
  320.     HASH[hash] = qt;
  321. }
  322.  
  323.  
  324.